/*
 * =====================================================================================
 *
 *       Filename:  StlKnowledge.cpp
 *
 *    Description:
 *
 *        Version:  1.0
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Yt(fndisme), fndisme@163.com
 *   Organization:
 *
 * =====================================================================================
 */
#include <cassert>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <list>
#include <map>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

static void vectorPart();
static void listPart();
static void mapPart();
static void setPart();
static void unorderedMapPart();
static void unorderedSetPart();
static void stlAlgorithm();

int main(int /* argc  */, char** /* argv */) {
	// stl 容器的基本知识（常识部分)
	vectorPart();
	listPart();
	mapPart();
	setPart();
	unorderedMapPart();
	unorderedSetPart();

	// 小小注意
	// set 并不会比 map 更省空间
	// 没有意外的情况下，优先考虑vector (why?)
	// log(n)的查找 和 近似 log(1) 的查找
	// 迭代器失效

	// stl 算法部分 常识部分
	stlAlgorithm();
}

static void vectorPart() {
	// c++ 11 and above
	using Group = std::vector<int>;
	// typedef
	// typedef std::vector<int> IntVector;
	Group a;
	a.push_back(10); // no push_front
	a.pop_back(); // no pop_front
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 10; ++i) a.emplace_back(i);

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		std::cout << *iter << " ";
	}
	std::cout << std::endl;

	// 通过索引
	for(int i = 0; i < a.size(); ++i) {
		std::cout << a[i]  << " ";
	}
	std::cout << std::endl;

}


static void listPart() {
	// c++ 11 and above
	using Group = std::list<int>;
	Group a;
	a.push_back(10);
	a.push_front(11);
	a.pop_back();
	a.pop_front();
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 5; ++i) a.emplace_back(i);
	for(int i = 5; i < 10; ++i) a.emplace_front(i);

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		std::cout << *iter << " ";
	}
	std::cout << std::endl;

}


static void mapPart() {
	// c++ 11 and above
	// map 默认的是用的std::less
	using Group = std::map<int, int>;
	Group a;
	auto ok = a.insert(std::make_pair(1,1)).second; // 注意返回值
	a[2] = 2; // 使用 [] 是有要求的
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 10; ++i) a.emplace(i, i); // 注意emplace本身是有返回值的

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		// 注意迭代器访问的输出的key是有顺序的
		std::cout << "key: " << (*iter).first << " value: " << iter->second << " ";
	}
	std::cout << std::endl;

	// 通过key索引
	for(int i = 0; i < a.size(); ++i) {
		std::cout << a.at(i) << " "; // 注意a[i]的区别
	}

	std::cout << std::endl;
}


static void setPart() {
	// c++ 11 and above
	// set 默认的是用的std::less
	using Group = std::set<int>;
	Group a;
	auto ok = a.insert(1).second; // 注意返回值
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 10; ++i) a.emplace(i); // 注意emplace本身是有返回值的

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		// 注意迭代器访问的输出的是有顺序的
		std::cout << " value: " << *iter << " ";
	}
	std::cout << std::endl;
}

static void unorderedMapPart() {
	// c++ 11 and above
	// why not name hash_map? 为了保证代码的兼容
	using Group = std::unordered_map<int, int>;
	Group a;
	auto ok = a.insert(std::make_pair(1,1)).second; // 注意返回值
	a[2] = 2; // 使用 [] 是有要求的
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 10; ++i) a.emplace(i, i); // 注意emplace本身是有返回值的

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		// 注意迭代器访问的输出是无序的
		std::cout << "key: " << (*iter).first << " value: " << iter->second << " ";
	}
	std::cout << std::endl;

	// 通过key索引
	for(int i = 0; i < a.size(); ++i) {
		std::cout << a.at(i) << " "; // 注意a[i]的区别
	}

	a.rehash(10); // ? 干了什么事情呢？
	std::cout << std::endl;
}


static void unorderedSetPart() {
	// c++ 11 and above
	using Group = std::unordered_set<int>;
	Group a;
	auto ok = a.insert(1).second; // 注意返回值
	a.size();
	auto isEmpty = a.empty();
	for(int i = 0; i < 10; ++i) a.emplace(i); // 注意emplace本身是有返回值的

	// 通过迭代器
	for(auto iter = a.begin(), iterEnd = a.end(); iter != iterEnd; ++iter) {
		// 注意迭代器访问的输出的是有顺序的
		std::cout << " value: " << *iter << " ";
	}
	std::cout << std::endl;
}

static void printInfoVersionOne();
static void sortPart();

static void stlAlgorithm() {
	// sort stable_sort
	// remove
	// find find_if
	// count count_if
	// copy copy_if (c++11)
	// swap (非常非常重要的一个函数，意想不到的重要)
	// random_shuffle shuffle
	// .......等等，请自行google
	// stl本身给我们提供了非常非常多的算法，可以替我们解决很多基本的问题，
	// 我们没有必要重新造轮子
	//
	// 一个矫情的例子
	printInfoVersionOne();

	sortPart();
}

static void printInfoVersionOne() {
  using DataStruct = std::vector<std::map<int, std::vector<int>>>;
  DataStruct complicateData;
  // fill data
  // 遍历所有的数据
  for (auto iterOne = complicateData.begin(); iterOne != complicateData.end();
       ++iterOne) {
    // do lot of things
    // ba ba ba
    // ba ba ba
    for (auto iterTwo = (*iterOne).begin(); iterTwo != (*iterOne).end();
         ++iterTwo) {
      // do lot of things
      // ba ba ba
      // ba ba ba
      for (auto iterThree = (*iterTwo).second.begin();
           iterThree != (*iterTwo).second.end(); ++iterThree) {

        // do lot of things
        // ba ba ba
        // ba ba ba
        // final we get the data
      }
    }
  }
}

static void sortPart() {
  std::vector<int> objects(1000);
  std::generate(std::begin(objects), std::end(objects),
                []() { return rand(); });
  std::sort(std::begin(objects), std::end(objects));
  auto seed = std::chrono::system_clock::now().time_since_epoch().count();
	auto engine = std::default_random_engine(seed);
  std::shuffle(std::begin(objects), std::end(objects),
               engine);
	auto objects2{objects};
	std::stable_sort(std::begin(objects), std::end(objects));
  std::shuffle(std::begin(objects), std::end(objects),
               engine);
}
